package stackAndQueue;

import java.util.*;

class MinStack1 {
    private final Deque<Integer> normalStack = new LinkedList<>();
    private final Deque<Integer> minStack = new LinkedList<>();


    public MinStack1() {

    }

    public void push(int val) {
        // 先找到当前的最小值，记为 min，再往 minStack 里压一次
        // 当前的最小值：
        // 1）minStack.isEmpty() => val
        // 2）!minStack.isEmpty() && val < minStack.peek() => val
        // 3）!minStack.isEmpty() && val > minStack.peek() => minStack.peek()
        // 4）!minStack.isEmpty() && val == minStack.peek() => val 或者 minStack.peek() 都行
        int min = val;
        if (!minStack.isEmpty() && val > minStack.peek()) {//大于，就重复放 min
            min = minStack.peek();
        }

        // 接下来就是 normalStack 压入 val；minStack 压入 min
        normalStack.push(val);
        minStack.push(min);
    }

    public void pop() {
        if (normalStack.isEmpty()) {
            return;
        }
        //change 无脑 同步 pop
        normalStack.pop();
        minStack.pop();
    }

    public int top() {
        if (normalStack.isEmpty()) {
            return -1;
        }

        return normalStack.peek();
    }

    public int getMin() {
        if (normalStack.isEmpty()) {
            return -1;
        }

        return minStack.peek();
    }

    public static void main(String[] args) {
        MinStack1 stack = new MinStack1();

        stack.push(5);
        stack.push(3);
        stack.push(7);
        stack.push(1);
        stack.push(1);
        stack.push(0);

        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
    }
}
